package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

//[151]反转字符串中的单词
public class ReverseWordsInAString151 {
    public static void main(String[] args) {
        Solution solution = new ReverseWordsInAString151().new Solution();
//    String the_sky_is_blue = solution.reverseWords("the sky is blue");
        String the_sky_is_blue = solution.reverseWords("  hello world  ");
//        String the_sky_is_blue = solution.reverseWords("a good   example");
//        String the_sky_is_blue = solution.reverseWords("wU G n F0m 1rT3zH 0Dtb8qG91w ruJO EQ  x9 a5YKNyuG VnUhxK o 1AM dpIMVv2SG 2zPeO 3c");
        System.out.println("ReverseWordsInAString151:main:" + the_sky_is_blue);

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 1ms 100%
        // 新建 数组，
        // 双指针 手动 copy .
        public String reverseWords(String s) {
            if (s == null || s.length() < 1) return s;
            char[] src = s.toCharArray();
            int len = src.length;

            //新字符数组
            char[] res = new char[len];
            int originIndex = len -1;
            int resIndex = 0;

            //最后一个 字母的位置
            int lastPosition = 0;

            while (originIndex >= 0){
                //跳过空格
                while (originIndex >= 0 && src[originIndex]==' ')originIndex--;

                //取出单词
                int wordEnd = originIndex;
                while (originIndex >= 0 && src[originIndex]!=' '){
                    originIndex--;
                }
                 int wordStart = originIndex+1;

                //赋值 单词。
                for (int i = wordStart; i <= wordEnd ; i++) {
                    res[resIndex] = src[i];
                    resIndex++;
                    lastPosition = resIndex;
                }

                //+ 空格
                if (resIndex < len){// 防止超了 len 加 ' '
                    res[resIndex]=' ';
                    resIndex++;
                }
            }
            return new String(res,0,lastPosition);//offset ,count.
        }

        // 8 ms
        //链接：https://leetcode.cn/problems/reverse-words-in-a-string/solution/fan-zhuan-zi-fu-chuan-li-de-dan-ci-by-leetcode-sol/
        public String reverseWordsOrg(String s) {
            //s.trim() 除去开头和末尾的空白字符  !!!重点。去掉后 s.split(\\s+) 就不会有 "" 了。
            s = s.trim();
            // 正则匹配连续的空白字符作为分隔符分割
            List<String> wordList = Arrays.asList(s.split("\\s+"));
            Collections.reverse(wordList);
            return String.join(" ", wordList);
        }

        //1 分割
        //2 头尾 指针交换
        //3 list cache word 最后组装。
        //排除 ""
        // 6 ms
        public String reverseWordsMFirst(String s) {
            if (s == null || s.length() < 1) return s;


//            String[] s1 = s.split("\\s+");//排除 "" 。前提是没有 【首尾 " "】
            String[] s1 = s.split(" ");
            StringBuilder sb = new StringBuilder();

            int left = 0, right = s1.length - 1;

            LinkedList<String> rightQue = new LinkedList<>();
            LinkedList<String> leftQue = new LinkedList<>();
            while (left <= right) {//"world" 1个单词的情况
                while ((left <= right) && (s1[left].equals(" ") || s1[left].equals(""))) ++left;

                while ((left <= right) && (s1[right].equals(" ") || s1[right].equals(""))) --right;
//                while ((left <= right)) ++left;
//
//                while ((left <= right)) --right;

                if (left > right){// !! 排除越界
                }else if (left == right) {// + " ",判断 左右边界
                    leftQue.offer(s1[left]);
                    left++;
                } else {
                    leftQue.offer(s1[left]);
                    rightQue.offer(s1[right]);
                    left++;
                    right--;
                }
            }

            //右边的放 前边
            int rightSize = rightQue.size();
            if (rightQue.size() > 0) {
                while (!rightQue.isEmpty()) {
                    sb.append(rightQue.poll());
                    if (rightQue.size() != 0) {//排除 队尾。后边判断。
                        sb.append(" ");
                    }
                }
            }

            //左边的放 后边
            if (leftQue.size() > 0) {
                while (!leftQue.isEmpty()) {
                    if (rightSize > 0) {//队首。如果 前面有。加上" "
                        sb.append(" ");
                    }
                    sb.append(leftQue.pollLast());
                }
            }
            return sb.toString();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}